
package com.coldchain.common.util;



import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

public class EvalLike {
    private static final Logger log= LoggerFactory.getLogger(EvalLike.class);
    // main
    public static void main(String []args) {
        String exp = "3 + 3 * 2 * ( 3 + (3 * 6) + 4 ) + 2";
        System.out.println(eval(exp));

    }

    // 各个符号的常量, 匹配的符号映射, 各个符号的优先级
    private final static char ADD = '+';
    private final static char SUB = '-';
    private final static char MUL = '*';
    private final static char DIV = '/';
    private final static char MOD = '%';
    private final static char LEFT_BRACKET = '(';
    private final static char RIGHT_BRACKET = ')';
    private final static Map<Character, Character> matched = new HashMap<>();
    private static Map<Character, Integer> priority = new HashMap<>();

    // 初始化
    static {
        matched.put(LEFT_BRACKET, RIGHT_BRACKET);

        priority.put(ADD, 0);
        priority.put(SUB, 0);
        priority.put(MUL, 1);
        priority.put(DIV, 1);
        priority.put(MOD, 1);
        priority.put(LEFT_BRACKET, 2);
        priority.put(RIGHT_BRACKET, 2);
    }

    // 先统计出exp中各个符号的位置  在用eval0真正计算
    // 首先记录所有的符号的位置, 添加到一个符号列表中[如果 有子计算过程, 递归计算]
    // 然后  计算给定的表达式
    public static int eval(String exp) {
        // Operator, Operation
        List<Integer> resInBrackets = new LinkedList<>();
        List<Operator> optr = new LinkedList<Operator>();
        for(int i=0; i<exp.length(); i++) {
            char c = exp.charAt(i);
            switch (c ) {
                case ADD :
                case SUB :
                case MUL :
                case DIV :
                case MOD :
                    optr.add(new Operator(c, i));
                    break;
                case LEFT_BRACKET :
                    int nextI = getNextMatched(exp, i+1, LEFT_BRACKET);
                    resInBrackets.add(eval(exp.substring(i+1, nextI)) );
                    optr.add(new Operator(LEFT_BRACKET, i) );
                    optr.add(new Operator(RIGHT_BRACKET, nextI) );
                    i = nextI;
                default :
                    break;
            }
        }
        int val = eval0(exp, optr, resInBrackets, null);


        return val;
    }

    // 计算给定的表达式  从首 -> 尾
    // 获取第一个操作数作为默认的返回值
        // 然后 获取第一个操作符, 以及下一个操作符
        // 如果下一个操作符的优先级大于当前操作符, 递归计算(当前结果, 第一个操作符之后的部分) [这里可以为本方法添加两个参数, 将带return的递归构造成尾递归, 不过这里  就不做了]
            // 否则  计算第一个操作符旁边的两个操作数, 循环, 直到操作符列表中只剩下一个操作符
    // 计算最后一个操作符  二边的操作数
    private static int eval0(String exp, List<Operator> optr, List<Integer> resInBrackets, Operator lastOptNow) {
        int res = 0;
        if(lastOptNow == null) {
            Operator firstOpt = optr.get(0);
            if(firstOpt.oper == LEFT_BRACKET) {
                optr.remove(0);
                optr.remove(0);
                res = resInBrackets.remove(0);
            } else {
                res = parseFirstInt(exp, firstOpt );
            }
        } else {
            res = parseInt(exp, lastOptNow, optr.get(0) );
        }

        while(optr.size() > 1) {
            Operator optNow = optr.get(0);
            Operator optNext = optr.get(1);
            optr.remove(0);
            if(priority.get(optNext.oper) > priority.get(optNow.oper) ) {
                if(optNext.oper == LEFT_BRACKET) {
                    Operator optNNext = null;
                    if(optr.size() > 2) {
                        optNNext = optr.get(2);
                    }
                    if((optNNext != null) && (priority.get(optNNext.oper) > priority.get(optNow.oper)) ) {
                        return calc(res, optNow, eval0(exp, optr, resInBrackets, null) );
                    } else {
                        optr.remove(0);
                        optr.remove(0);
                        res = calc(res, optNow, resInBrackets.remove(0) );
                    }
                } else {
                    return calc(res, optNow, eval0(exp, optr, resInBrackets, optNow) );
                }
            } else {
                res = calc(res, optNow, parseInt(exp, optNow, optNext) );
            }
        }

        if(optr.size() > 0) {
            res = calc(res, optr.get(0), parseLastInt(exp, optr.get(0)) );
        }

        return res;
    }

    // 计算val01, val02  的opt操作  返回结果
    private static int calc(int val01, Operator opt, int val02) {   
        int val = 0;
        switch(opt.oper) {
            case ADD :
                val = val01 + val02;
                break;
            case SUB :
                val = val01 - val02;
                break;
            case MUL :
                val = val01 * val02;
                break;
            case DIV :
                val = val01 / val02;
                break;
            case MOD :
                val = val01 % val02;
                break;
        }

        return val;
    }

    // 解析当前云算符 和下一个云算法之间的的操作数
    private static int parseInt(String exp, Operator optNow, Operator optNext) {
        String intStr = null;
        try {
            intStr = exp.substring(optNow.index+1, optNext.index).trim();
            return Integer.parseInt(intStr);
        } catch (Exception e) {
            log.error("error while parse first operand[idx : " + optNow.index + "][' " + intStr + " '] !");
            throw e;
        }
    }
    private static int parseLastInt(String exp, Operator optNow) {
        try {
            return Integer.parseInt(exp.substring(optNow.index+1).trim() );
        } catch(Exception e) {
            log.error("error while parse last operand[idx : " + optNow.index + "] !");
            throw e;
        }
    }
    private static int parseFirstInt(String exp, Operator optNow) {
        try {
            return Integer.parseInt(exp.substring(0, optNow.index).trim() );
        } catch(Exception e) {
            log.error("error while parse first operand[idx : " + optNow.index + "] !");
            throw e;
        }
    }

    // 获取当前位置的符号匹配的下一个符号
    private static int getNextMatched(String exp, int idx, char left) {
        Deque<Character> stack = new LinkedList<>();
        stack.push(left);
        for(int i=idx; i<exp.length(); i++) {
            char ch = exp.charAt(i);
            if(matched.containsKey(ch) ) {
                stack.push(ch);
            }
            if(ch == matched.get(stack.peek()) ) {
                stack.pop();
                if(stack.size() == 0) {
                    idx = i;
                    break ;
                }
            }
        }

        return idx;
    }

    // --------------- bean --------------------

    // 封装每一个操作符   以及其索引
    static class Operator {
        // 操作符, 索引
        char oper;
        int index;

        // 初始化
        public Operator() {

        }
        public Operator(char oper, int index) {
            this.oper = oper;
            this.index = index;
        }

        // for debug ..
        public String toString() {
            return oper + " -> " + index + "; ";
        }
    }

}